#define _CRT_SECURE_NO_WARNINGS
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
void swap(int* x, int* y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
    if (listsSize == 0)
        return NULL;
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->next = lists[0];
    struct ListNode* ptail = NULL;
    struct ListNode* pre = head->next;
    struct ListNode* cur = head;
    while (cur->next)
        cur = cur->next;
    for (int i = 1; i < listsSize; i++) {
        cur->next = lists[i];
        while (cur->next)
            cur = cur->next;
    }
    if (pre)
        ptail = pre->next;
    struct ListNode* check = head->next;
    int cnt = 0;
    while (check)
    {
        cnt++;
        check = check->next;
    }
    for (int j = 0; j < cnt; j++)
    {
        while (ptail)
        {
            if (pre->val > ptail->val)
                swap(&pre->val, &ptail->val);
            pre = ptail;
            ptail = ptail->next;
        }
        pre = head->next;
        if (pre)
            ptail = pre->next;
    }
    return head->next;
}